package jago02.jago0201.ag01_sort;

import java.util.Arrays;

/**
 * 快速排序
 * 杂化简：采用分治算法，将原数组反复根据分界值，将小于分界值的放于数组左边，大于分界值的放于数组右边，分界值左右两边的子数组按相同方式继续重复操作
 * 解目录：
 *      0.取数组最低索引位为分界值，在数组头尾各定义一个指针，一个从左往右找大于分界值的，一个从右往左找小于分界值的，找到后交换
 *      1.重复上面操作直到两个指针相等，扫描结束，指针位置是分界值真正应该存放的位置，交换默认分界值位置和指针位置的元素，从而最终获取分界值位置索引
 *      2.根据获取的分界值位置，将数组分为左数组(0,part-1)和右数组(part+1,arr.length-1)，然后左右数组继续重复上述操作
 * 复杂度：O(NLogN)
 */
public class Sort06_Quick {

    public static void main(String[] args) {
        Comparable[] arr = new Comparable[]{1,5,2,3,4,6,8,0};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void sort(Comparable[] arr) {
        int low = 0;
        int hight = arr.length-1;
        sort(arr,low,hight);
    }

    private static void sort(Comparable[] arr, int low, int hight) {
        if (low>=hight){
            return;
        }
        //找到分界位置
        int partition = partition(arr,low,hight);
        //分解左侧数组排序
        sort(arr,low,partition-1);
        //分解右侧数组排序
        sort(arr,partition+1,hight);
    }

    private static int partition(Comparable[] arr, int low, int hight) {
        //默认分界值
        Comparable partValue = arr[low];
        //定义两个指针分别为最小索引和最大索引+1
        int left = low;
        int right = hight+1;
        //切分
        while (true){
            //先从右往左扫描，找到小于默认分界值的
            while (lessThan(partValue,arr[--right])){
                if (right==low){
                    break;
                }
            }
            //再从左往右扫描，找到大于默认分界值的
            while (lessThan(arr[++left],partValue)){
                if (left==hight){
                    break;
                }
            }
            //扫描结束
            if (left>=right){
                break;
            }else {
                exch(arr,left,right);
            }

        }
        //上面循环结束时，left == right，将默认分界值放到left/right位置上
        exch(arr,low,right);
        return right;
    }


    private static void exch(Comparable[] arr, int j, int i) {
        Comparable tmp = arr[j];
        arr[j] = arr[i];
        arr[i] = tmp;
    }

    private static boolean lessThan(Comparable m, Comparable n) {
       return m.compareTo(n)<0;
    }
    private static boolean bigThan(Comparable m, Comparable n) {
       return m.compareTo(n)>0;
    }
}
